<!--
 * @Author: your name
 * @Date: 2021-08-09 17:12:45
 * @LastEditTime: 2021-08-10 14:35:56
 * @Description: 
-->
<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>归并排序</title>
</head>

<body>
  <img src="../images/mergeSort.png" alt="">
  <p>归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；</p>
  <p>其次是“治”，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小</p>
  <p>“分”就是将原始数组逐次二分，直到每个数组只剩一个元素，一个元素的数组自然是有序的，所以就可以开始“治”的过程了。</p>
  <p>“治”实际上是将已经有序的数组合并为更大的有序数组</p>
  <p>如数组[4,6,1]拆分为[4][6][1]，然后对比合并[4][6] => [4,6][1] => [1,4,6]</p>
  <a href="https://www.cnblogs.com/lyt0207/p/12489144.html">
    https://www.cnblogs.com/lyt0207/p/12489144.html
  </a>

  <script>
    // 1. 递归把数组拆为n个数组，每个数组一个元素
    function mergeSort(array) {
      const len = array.length
      if (len < 2) return array

      const middle = Math.floor(len / 2)
      const left = array.slice(0, middle)
      const right = array.slice(middle, len)
      const mergeSortLeft = mergeSort(left)
      const mergeSortRight = mergeSort(right)
      // 2. 对比合并数组
      const result = merge(mergeSortLeft, mergeSortRight)
      return result
    }

    function merge(left, right) {
      
      // 定义左右两个数组的索引
      let [leftIndex, rightIndex] = [0, 0]
      // 定义最终结果值
      let result = []
      // 循环比较左右两个数组的元素，直到左或右数组索引值大于数组长度
      while (leftIndex < left.length && rightIndex < right.length) {
        
        // 如果左数组元素小，就添加进最终结果并且左数组索引加一
        if (left[leftIndex] <= right[rightIndex]) {
          result.push(left[leftIndex])
          leftIndex++
        } else {// 如果右数组元素小，就添加进最终结果并且右数组索引加一
          result.push(right[rightIndex])
          rightIndex++
        }
      }
      
      // 上面循环有一个数组索引值先大于数组长度，另一个数组会剩一个元素，
      // 所以这里把最后一个元素拿出来合并到result
      console.log(leftIndex, rightIndex)
      result = result.concat(left.slice(leftIndex, left.length))
      result = result.concat(right.slice(rightIndex, right.length))
      
      return result
    }

    console.log(mergeSort([2, 8, 3, 1, 5, 2, 7, 4, 33, 11, 0]))
  </script>
</body>

</html>